package 中等.贪心思想;

import java.util.Arrays;

/**
 * 你正在玩一个单人游戏，面前放置着大小分别为 a、b 和 c的 三堆 石子。
 * 每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上
 * 加 1 分。当存在 两个或更多 的空堆时，游戏停止。
 * 给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-score-from-removing-stones
 */
public class 移除石子的最大得分_1753 {

    public static void main(String[] args) {

        System.out.println(maximumScore2(4, 4, 6));

    }

    /**
     * 贪心+模拟
     * 每次优先选择最大和第二大堆的石子-1
     */
    public static int maximumScore(int a, int b, int c) {
        int score = 0;
        int[] arr = new int[3];
        arr[0] = a;
        arr[1] = b;
        arr[2] = c;
        Arrays.sort(arr);
        while (arr[1] != 0) {
            if (arr[0] == 0) {
                return score + arr[1];
            }
            int curScore = arr[1] - arr[0] + 1;
            score += curScore;
            arr[1] -= curScore;
            arr[2] -= curScore;
            Arrays.sort(arr);
        }
        return score;
    }

    /**
     * 贪心+分类讨论
     * 假设 a<=b<=c
     * 如果 a+b <=c ，那么 a 和 b 都和 c 进行抵消，可以将 a 和 b 降低到 0 ,
     * 答案为 a+b
     * 如果 a+b > c ，那么 c 先去抵消 b-a 的差，一定可以使得
     * a == b ,然后 a,b 相互抵消，因为 b<=c ，所以 b-a<=c，即一定存在
     * c1+c2=c 使得 a-c1 == b-c2
     * (a-c1+b-c2)/2+c = (a+b+c)/2 = 最大得分
     */
    public static int maximumScore2(int a, int b, int c) {
        int sum = a + b + c;
        int max = Math.max(a, Math.max(b, c));

        // a+b<=c
        if (sum - max <= max) {
            return sum - max;
        } else {
            return sum / 2;
        }
    }

}
